class Solution:
    def numIslands(self, grid) -> int:
        id = 1
        gridId = [[None for _ in range(len(grid[x]))] for x in range(len(grid))]
        relation = set()
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == '0':
                    continue
                if i == 0:
                    if j == 0:
                        gridId[i][j] = id
                        id = id + 1
                    else:
                        if gridId[i][j - 1] :
                            gridId[i][j] = gridId[i][j - 1]
                        else:
                            gridId[i][j] = id
                            id = id + 1
                else:
                    if j == 0:
                        if gridId[i - 1][j]:
                            gridId[i][j] = gridId[i - 1][j]
                        else:
                            gridId[i][j] = id
                            id = id + 1
                    else:
                        if gridId[i - 1][j]:
                            if gridId[i][j - 1]:
                                if gridId[i - 1][j] < gridId[i][j - 1]:
                                    relation.add((gridId[i - 1][j], gridId[i][j - 1]))
                                elif gridId[i - 1][j] > gridId[i][j - 1]:
                                    relation.add((gridId[i][j - 1], gridId[i - 1][j]))
                            gridId[i][j] = gridId[i - 1][j]
                        else:
                            if gridId[i][j - 1]:
                                gridId[i][j] = gridId[i][j - 1]
                            else:
                                gridId[i][j] = id
                                id = id + 1
        # 将关系分堆
        ids = [i for i in range(id)]
        for x, y in relation:
            xi = ids[x]
            yi = ids[y]
            if xi < yi:
                for i in range(len(ids)):
                    if ids[i] == yi:
                        ids[i] = xi
            elif xi > yi:
                for i in range(len(ids)):
                    if ids[i] == xi:
                        ids[i] = yi
        return len(set(ids)) - 1


if __name__ == '__main__':
    so = Solution()
    #     s = """
    # 11111
    # 11000
    # 00101
    # 00011"""
    #     s = s[1:]
    #     s = s.split("\n")
    #     s = [list(x) for x in s]
    #     print(s)
    # s = [["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "0", "1", "1"],
    #      ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "0"],
    #      ["1", "0", "1", "1", "1", "0", "0", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "0", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1"],
    #      ["0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "0", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1"],
    #      ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1", "1", "1", "0", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "1", "1", "0"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1", "0", "0"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"],
    #      ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]]
    s = [["1","1","1","1","0"],
         ["1","1","0","1","0"],
         ["1","1","0","0","0"],
         ["0","0","0","0","0"]]
    k = [[0, 0, 0, 0, None],
         [1, 1, None, 2, None],
         [1, 1, None, None, None],
         [None, None, None, None, None]]
    r = so.numIslands(s)
    print(r)
